public class MyLikendList {
    public class NNode {

        private int value;
        private NNode next;

        public NNode() {
        }

        public NNode(int x) {
            this.value = x;
        }
    }

    public NNode head;//链表的头节点

    public void display() {
        NNode cur = head;
        if (head == null) {
            System.out.print("链表为空");
        }
        while (cur != null) {
            System.out.print(cur.value + " ");
            cur = cur.next;
        }
        System.out.println();
    }
    public void display(NNode newHead) {
        NNode cur = newHead;
        if (newHead == null) {
            System.out.print("链表为空");
        }
        while (cur != null) {
            System.out.print(cur.value + " ");
            cur = cur.next;
        }
        System.out.println();
    }

    public int size() {
        /*if (head == null) {
            return 0;
        }*/
        NNode cur = head;
        int count = 0;
        while (cur != null) {
            count++;
            cur = cur.next;
        }
        return count;
    }

    public void addFirst(int x) {
        NNode NNode = new NNode(x);
        NNode.next = head;
        head = NNode;
    }

    public void addLast(int x) {
        NNode NNode = new NNode(x);
        if (head == null) {
            head = NNode;
            return;
        }
        NNode cur = head;
        while (cur.next != null) {
            cur = cur.next;
        }
        cur.next = NNode;
    }

    public void addIndex(int y, int x) {
        NNode NNode = new NNode(x);
        int size = this.size();
        if (y < 0 || y > size) {
            System.out.println("插入位置不合法");
            return;
        }
        if (y == 0) {
            addFirst(x);
            return;
        }
        if (y == size) {
            addLast(x);
            return;
        }
        NNode cur = head;
        for (int i = 1; i < y; i++) {
            cur = cur.next;
        }
        NNode.next = cur.next;
        cur.next = NNode;
    }

    public void remove(int y) {
        int size = this.size();
        if (y < 0 || y >= size) {
            System.out.println("删除位置不合法");
            return;
        }
        if (y == 0) {
            head = head.next;
            return;
        }
        NNode cur = head;
        for (int i = 1; i < y; i++) {
            cur = cur.next;
        }
        cur.next = cur.next.next;
    }

    public void reverse() {
        if (this.size()<0){
            System.out.println("链表不存在");
            return;
        }
        NNode cur = head.next;
        head.next = null;
        NNode pel;
       while (cur != null){
           pel = cur.next;
           cur.next = head;
           head = cur;
           cur = pel;
       }
    }
    public NNode reverse(int x) {
        if (this.size()< x || x < 0){
            System.out.println("反转位置不合法");
            return null;
        }
        //找到转换前的位置
        NNode newHead = head;
        for (int i = 0; i < x-1; i++) {
            newHead = newHead.next;
        }
        if (newHead.next.next == null){
            System.out.println("反转位置已是最后位置");
            return null;
        }
        NNode doHead = newHead.next;
        NNode cur = doHead.next;
        doHead.next = null;
        NNode pel;
        while (cur != null){
            pel = cur.next;
            cur.next = doHead;
            doHead = cur;
            cur = pel;
        }
        newHead.next = doHead;
        return doHead;
    }
    public NNode merge(MyLikendList x,MyLikendList y){
        if (x.head == null){
            return y.head;
        }
        if (y.head == null){
            return x.head;
        }
        NNode newHead = new NNode();
        NNode tmp = newHead;
        while (x.head != null && y.head != null){
            if (x.head.value > y.head.value){
                tmp.next = y.head;
                tmp = y.head;
                y.head = y.head.next;
            }else {
                tmp.next = x.head;
                tmp = x.head;
                x.head = x.head.next;
            }
        }
        if (x.head == null){
            tmp.next = y.head;
        }
        if (y.head == null){
            tmp.next = x.head;
        }
        return newHead.next;
    }
}
